/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 涛
 * Date: 2023-09-30
 * Time: 10:26
 */
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class question4 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newH = new ListNode();
        ListNode tmpH = newH;

        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                tmpH.next = list1;
                list1 = list1.next;

            } else {
                tmpH.next = list2;
                list2 = list2.next;

            }
            tmpH = tmpH.next;
        }
        if(list1 != null) {
            tmpH.next = list1;
        }
        if(list2 != null) {
            tmpH.next =list2;
        }
        return newH.next;
    }
}
class question3 {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode cur = head;
        int len = 0;
        //求链表的长度
        while(cur != null) {
            cur = cur.next;
            len++;
        }
        //判断K下标的合法性
        if(k <= 0 || k > len) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;
        for(int i = 0; i < k - 1; i++) {
            fast = fast.next;
        }

        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}
class question2 {
    public ListNode middleNode(ListNode head) {
        int size = 0;
        ListNode cur = head;
        //一个节点都没有
        if(head == null) {
            return null;
        }
        //只有一个节点
        if(head.next == null) {
            return head;
        }
        //遍历一遍链表，求出链表长度
        while(cur != null) {
            cur = cur.next;
            size++;
        }
        cur = head;
        //奇数
        if(size % 2 != 0) {
            for(int i = 0; i < (size - 1) / 2; i++) {
                cur = cur.next;
            }
            return cur;
        } else { //偶数
            for(int i = 0; i < size / 2; i++) {
                cur = cur.next;
            }
            return cur;
        }
    }
}
class question1 {
    public ListNode reverseList(ListNode head) {
        //一个节点都没有
        if(head == null) {
            return null;
        }
        //只有一个节点
        if(head.next == null) {
            return head;
        }
        //多个节点
        ListNode cur = head.next;
        head.next = null;

        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
}
public class Test1 {

}
